package 二叉搜索树;

class BinarySearchTree {
    //静态内部类
    public static class Node{
        public int val;
        public Node left;
        public Node right;

        public Node(int val) {
            this.val = val;
        }
    }

    public Node root;

    /**
     * 二叉搜索树的插入
     * 注意！！！当插入已经存在的值时，会插入失败！！！
     * 每次插入 一定是 插入到 叶子结点的地方
     */
    public boolean insert(int key) {
        Node node=new Node(key);
        if (root==null) {
            root=node;
            return true;
        }

        Node cur=root;
        Node parent=null;

        while (cur!=null) {
            if (cur.val==key) {
                return false;//二叉搜索树中 不能插入 已经存在的值
            }else if (cur.val<key) {
                parent=cur;
                cur=cur.right;
            }else {
                parent=cur;
                cur=cur.left;
            }
        }

        //出while循环后，cur指向null,parent指向当前叶子结点，和叶子节点的值进行比较完成插入
        if (parent.val<key) {
            parent.right=node;
        }else {
            parent.left=node;
        }
        return true;
    }

    /**
     * 二叉搜索树的查找
     * 从根节点开始 查找 值为key的结点
     */
    public Node search(int key) {
        Node cur=root;
        while (cur!=null) {
            if (cur.val==key) {
                return cur;
            }else if (cur.val<key) {
                cur=cur.right;
            }else {
                cur=cur.left;
            }
        }
        return null;
    }

    /**
     * 二叉树搜索树的删除
     * 难点！！！
     * 待删除结点cur 的左右元素都不为空
     * 找个替罪羊
     * 在待删除结点cur的 右子树中找到最左边的结点，
     * 或者 在待删除结点cur的 左子树中找到最右边的结点。
     * 替罪羊的值替换cur的值后，再 删除替罪羊(因为替罪羊一定符合 左为空或右为空)
     */
    public void remove(Node parent,Node cur) {
        if (cur.left==null) {
            // 待删除结点cur 的 左边元素为空时
            if (cur==root) {
                root=cur.right;
            }else if (cur==parent.left) {
                parent.left=cur.right;
            }else {
                //cur==parent.right
                parent.right=cur.right;
            }
        }else if (cur.right==null) {
            // 待删除结点cur 的 右边元素为空时
            if (cur==root) {
                root=cur.left;
            }else if (cur==parent.left) {
                parent.left=cur.left;
            }else {
                //cur==parent.right
                parent.right=cur.left;
            }
        }else {
            // 待删除结点cur 的左右元素都不为空时，处理就会复杂些
            // 找个替罪羊
            // 在待删除结点cur的 右子树中找到最左边的结点，能够保证放到cur位置后，它的左子树都比它大
            // 或者
            // 在待删除结点cur的 左子树中找到最右边的结点，能够保证放到cur位置后，它的右子树都比它小
            // 替罪羊的值替换cur的值后，再 删除替罪羊(因为替罪羊一定符合 左为空或右为空)

            //以 右子树中找到最左边的结点为替罪羊为例
            Node target=cur.right;
            Node targetParent=cur;
            while (target.left!=null) {
                targetParent=target;
                target=target.left;
            }

            cur.val=target.val;
            if (target==targetParent.left) {
                targetParent.left=target.right;
            }else {
                //target==targetParent.right
                targetParent.right=target.right;
            }
        }

    }
    public void removeKey(int key) {
        if (root==null) {
            return;
        }
        Node cur=root;
        Node parent=null;

        while (cur!=null) {
            if (cur.val==key) {
                //进行删除
                remove(parent,cur);

            }else if (cur.val<key) {
                parent=cur;
                cur=cur.right;
            }else {
                parent=cur;
                cur=cur.left;
            }
        }
    }

}


public class TestDemo {
    public static void inOrder(BinarySearchTree.Node root) {
        if (root==null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    public static void preOrder(BinarySearchTree.Node root) {
        //BinarySearchTree.Node root
        //这样访问Node 是因为Node是BinarySearchTree的内部类
        if (root==null) {
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }



    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(13);
        binarySearchTree.insert(1);
        binarySearchTree.insert(21);
        binarySearchTree.insert(14);
        binarySearchTree.insert(5);
        binarySearchTree.insert(6);

        inOrder(binarySearchTree.root);
        System.out.println();
        preOrder(binarySearchTree.root);
        System.out.println();


//        System.out.println(binarySearchTree.search(1).val);
        binarySearchTree.removeKey(13);

        inOrder(binarySearchTree.root);
        System.out.println();
        preOrder(binarySearchTree.root);
        System.out.println();
    }
}
